#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;

class Solution
{
    int ans = 0;
    vector<vector<int>> adj;
    string label_str;
    bool memo[14][14][1 << 14];

    void dfs(int u, int v, int mask, bool isNotSingle)
    {
        if(memo[u][v][mask]){
            return;
        }
        memo[u][v][mask] = true;
        for (int next_u : adj[u])
        {
            for (int next_v : adj[v])
            {
                if (!(mask & (1 << next_u)) && !(mask & (1 << next_v)) && label_str[next_u] == label_str[next_v])
                {
                    // 如果 next_u 和 next_v 是同一个节点，路径不能再扩展
                    if (next_u == next_v)
                    {
                        ans = max(ans, __builtin_popcount(mask) + isNotSingle);
                        continue;
                    }
                    // 如果 next_u 和 next_v 是不同的节点
                    int new_mask = mask | (1 << next_u) | (1 << next_v);
                    ans = max(ans, __builtin_popcount(new_mask));
                    dfs(next_u, next_v, new_mask, isNotSingle);
                }
            }
        }
    }

public:
    int maxLen(int n, vector<vector<int>> &edges, string label)
    {
        if (n <= 1)
        {
            return n;
        }

        adj.assign(n, vector<int>());
        for (const auto &edge : edges)
        {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        this->label_str = label;
        this->ans = 1;

        for (const auto &edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            if (label[u] == label[v])
            {
                ans = max(ans, 2);
                int initial_mask = (1 << u) | (1 << v);
                dfs(u, v, initial_mask, true);
            }
        }

        for (int i = 0; i < n; ++i)
        {
            dfs(i, i, (1 << i), false);
        }

        return ans;
    }
};